1. Field of the Invention
The present invention relates to a directory entry (DENTRY) lookup apparatus and method for a storage device, and a data storage medium storing therein a directory entry lookup program, and more particularly, to a directory entry lookup method which can quickly find a directory entry of a target file in the storage device even if a target directory includes many files and which does not need to manage a data structure for quick lookup, and to a directory entry lookup apparatus, and a data storage medium storing therein a directory entry lookup program for performing the method, and further to a storage device configured to store the directory entries.
2. Description of the Related Art
One of the functions provided by a file system is a directory service. The file system manages an index node (inode) for each directory in the same way that it manages an inode for each file. The file system allows each directory entry, which is data about each of the files and subdirectories included in each directory, to be accessed from the inode for that directory in the same way that it allows data included in each file to be accessed from the inode for that file.
A process of quickly finding a file when desired by a user or generating and deleting a file is a major operation of the directory service. In particular, when a directory includes many files, it is very important to find a file quickly.
To find a target file in a directory that includes a plurality of files, a search method using a hash function, a tree-based search method, or the like may be used.
In the search method using the hash function, a target filename is converted into a value using a hash function, and a hash table is searched using an index corresponding to the value in order to find the position of a directory entry corresponding to the target filename. Since the position of a desired directory entry can be immediately found in the hash table, this method is the quickest search method in an ideal situation. However, the costs of processing hash collisions, of managing hash tables, and of managing empty directory entries are incurred.
Meanwhile, a tree-based search method uses a data structure such as a binary search tree which is widely known as a search method that can solve the hash collision problem of the search method using the hash function and reduce the cost of configuring a hash table. In this method, a tree structure is searched using a hash value for a target filename as a key value to find the position of a stored directory entry. The tree-based search method can achieve tolerable performance for a very large number of directory entries. However, since nodes are still generated for empty directory entries, there is wasted storage space occupied by a data structure for lookup of an empty directory.